package daythree;
/*1.遍历:
 * 深度遍历 
 * 宽度遍历 (层次遍历 )  这里 按照 卡尔的 算法 网站 学习 
 * 2.二叉树的序列化 (常考的 问题 很骚)  这个其实 已经 明白了差不多了 
 * 剩下 的 就是 代码了
 * 两种序列化 方式 :
 * 深度 序列化
 * 宽度序列化 :(层次序列化)
 * 
 * 
 * 3.树形DP (在树上 做动态规划  动态规划 : 用空间 换取时间 )
 * 又称   二叉树的递归套路:
 * 步骤:1.假设以 x 为头 可以向左树 和向右树 要  任何信息
 * 2. 在上一步的 基础下 讨论 以x为头的 图.树 得 到答案得 可能性(最重要)  常见的 分类 是 与 当前节点 有关 与当前节点无关
 * 3.列出所有 可能性 之后 确定 向左 右子树 要什么信息
 * 4.把左子树 和右子树得 收集到得信息 求全集  就是 任何 子树 都需要返回得 信息 S
 * 5递归 函数 都返回 S 每一棵 子树 都这样要求
 * 6. 写代码整合
 * 一下 是 相应的 题目  
 * ①给一个 树头 判断 是不是 平衡二叉树 :	
 *  
 * 
 *②:给出 一个 二叉树得 head 任何两个节点之间 都有 距离 求出 这个树得 两个节点之间 得最大距离
 *第三步 : 列出 所有得  可能 这是很关键的  地方 : 比如 这个题  以 x 节点 为例 ① 这个最大距离 跟 当前节点 没关 就是 最大距离 不经过
 *x节点 ②  x节点 是最大距离得 路径得中的一个  节点   
 *这个题 理解 高度 和 距离之间得  对应关系 就差不多了   
 * 
 * 
 * 
 题目③  : 判断 是不是 搜索 二叉树  求出 其 最大 子树的 节点个数   这个 并不是 简单 判断是不是 搜索二叉树 
 具体细节  直接看 代码 把
 
 
 
 
 题目 ④  : 公司 快乐值  的问题  这个题 涉及到多叉树 
 
 
 
 
 * 题目一:
 *如何设计一个函数 打印一棵树
 * 
 * 
 * 题目二:
 * 二叉树的结构定义如下:
 * Node{
 * int  value;
 * Node  left;
 * Node right;
 * Node parent;
 * }
 * 给你二叉树 的某个节点  写出其后继节点 (中序 遍历中 该节点的 后一个节点 就是 后继节点)
 * (拓展  找前驱节点 )
 * 
 * 
 */
public class Tree {
	static class Node {
		int value;
		Node left;
		Node right;
		public Node(int value) {
			this.value=value;
		}
	}
//题目 ③ 的code
	static class Information{
		int maxSubSize;
		boolean isBST;
		int max;
		int min;
		public Information(int m,int max,int min,boolean is) {
			maxSubSize=m;
			isBST=is;
			this.max=max;
			this.min=min;
		}
	}
	public static Information processBlackBox(Node head) {
		//  这个 树形DP 的问题 basecase 不能一下 全部 都设置好 所以直接返回null
		//  还一个 特别重要的点就是 判断 是否为   null  这很关键的
		if(head==null) {
			return null;
		}
		Information leftData =processBlackBox(head.left);
		Information rightData=processBlackBox(head.right);
		int min=head.value;
		int max=head.value;
		if(leftData!=null) {
			min=Math.min(min, leftData.min);
			max=Math.max(max, leftData.max);
		}
		if(rightData!=null) {
			min=Math.min(min, rightData.min);
			max=Math.max(max, rightData.max);
		}
		//  还剩下很多其他的  信息没有 补全
		// 剩下  的 之后 复习 来写 
		return null  ;
	}
	
// 题目②  的 code
	static class InforPlus{
		int height;
		int maxDistance;
		public InforPlus(int h,int max) {
			height=h;
			maxDistance=max;
		}
	}
	
	
	public static int maxDis(Node head) {
		return processPlus(head).maxDistance;
	}
	
	public static InforPlus processPlus(Node head) {
		if(head==null) {
			return new InforPlus(0,0);
		}
		
		InforPlus leftData=processPlus(head.left);
		InforPlus rightData = processPlus(head.right);
		int height=Math.max(leftData.height, rightData.height)+1;
		int maxD=Math.max(Math.max(leftData.maxDistance, rightData.maxDistance), leftData.height+rightData.height
				+1);
		// 返回 整合的 当前节点 应该返回的信息 
		return new InforPlus(height,maxD);
		
	}
	
	
	
	
	//题目 ① 得 code
	static class Infor {
		int height;
		boolean isBanlance;
		public Infor(boolean is,int h) {
			height=h;
			isBanlance=is;
		}
	}
	public static boolean isBST(Node head) {
		return  process(head).isBanlance;
	}
	public static Infor process(Node head) {
		if(head==null)
			return new Infor(true,0);
		// 左子树得 信息
		Infor leftData=process(head.left);
		// 右子树得  信息
		Infor rightData=process(head.right);
		boolean flag=leftData.isBanlance && rightData.isBanlance && (Math.abs(leftData.height
				-rightData.height)<2) ? true : false;
		int h= Math.max(leftData.height, rightData.height)+1;
		// 返回 整合 之后得  当前节点应该 返回得 信息
		return new Infor(flag,h);
		
	}
}
